class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        digit_alpha = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        def backtrace(digits, start, ans, cur_ans):
            if start == len(digits):
                if len(cur_ans) > 0:
                    ans.append("".join(cur_ans))
                return

            for alaph in digit_alpha[int(digits[start]) - 2]:
                cur_ans.append(alaph)
                backtrace(digits, start + 1, ans, cur_ans)
                cur_ans.pop()
        ans = []
        backtrace(digits, 0, ans, [])
        return ans
